"""
Problem 69: https://projecteuler.net/problem=69

Totient maximum

Euler's Totient function, φ(n) [sometimes called the phi function],
is used to determine the number of numbers less than n which are relatively prime to n.
For example, as 1, 2, 4, 5, 7, and 8,
are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	                1	    2
3	1,2	                2	    1.5
4	1,3	                2	    2
5	1,2,3,4	            4	    1.25
6	1,5		            2	    3
7	1,2,3,4,5,6	        6	    1.1666...
8	1,3,5,7		        4	    2
9	1,2,4,5,7,8	        6	    1.5
10	1,3,7,9	            4	    2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/24
'''




from commonfuncs.primefunctools import isPrime
def solution(limit: int = 1000000) -> list:
    '''
    φ(n) = n(1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk), pi is prime factor of n
    n/φ(n) = 1 /
              / (1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk)  
    so, max{ n/φ(n) }  
        <==> min{ (1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk) }

    we wish pi more and more, and as small as possible.
    so ,when n = 2*3*7*11*... < limit, n/φ(n) is a maximum

    for primes(<100) [2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 
    35, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 
    97], the product is 1210423181071397172995378627349171936750,
    so ,we just need primes less 100.

    >>> print(solution(9))
    (6, 2, 3.0, [2, 3])
    '''

    primes = [i for i in range(100) if isPrime(i)]

    res = 1
    i = 0
    phi = 1
    while True:
        res *= primes[i]
        phi *= primes[i]-1
        if res > limit:
            res //= primes[i]
            phi //= primes[i]-1
            break
        i += 1

    return res, phi, res/phi, primes[:i]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # (510510, 92160, 5.539388020833333, [2, 3, 5, 7, 11, 13, 17])
